// LeetCode Problem Nr. 146； LRU 缓存

/*
请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
    LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
    int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：
	输入
	["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
	[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
	输出
	[null, null, null, 1, null, -1, null, -1, 3, 4]

	解释
	LRUCache lRUCache = new LRUCache(2);
	lRUCache.put(1, 1); // 缓存是 {1=1}
	lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
	lRUCache.get(1);    // 返回 1
	lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
	lRUCache.get(2);    // 返回 -1 (未找到)
	lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
	lRUCache.get(1);    // 返回 -1 (未找到)
	lRUCache.get(3);    // 返回 3
	lRUCache.get(4);    // 返回 4

提示：
    1 <= capacity <= 3000
    0 <= key <= 10000
    0 <= value <= 105
    最多调用 2 * 105 次 get 和 put

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

type DoublyLinkedNode struct {
	key, value int
	previous, next *DoublyLinkedNode
}

type LRUCache struct {
	capacity int
	size int
	head, tail *DoublyLinkedNode
	mapper map[int]*DoublyLinkedNode
}


func Constructor(capacity int) LRUCache {
	cache := LRUCache{
		capacity: capacity,
		head: &DoublyLinkedNode{},
		tail: &DoublyLinkedNode{},
		mapper: make(map[int]*DoublyLinkedNode),
	}
	cache.head.next = cache.tail
	cache.tail.previous = cache.head
	return cache
}

func (c *LRUCache) removeNode(node *DoublyLinkedNode) {
	node.previous.next = node.next
	node.next.previous = node.previous
}

func (c *LRUCache) addToHead(node *DoublyLinkedNode) {
	node.previous = c.head
	node.next = c.head.next
	c.head.next = node
	node.next.previous = node
}




func (c *LRUCache) Get(key int) int {
	if node, ok := c.mapper[key]; !ok {
		return -1
	} else {
		if c.head.next != node {
			c.removeNode(node)
			c.addToHead(node)
		}
		return node.value
	}
}


func (c *LRUCache) Put(key int, value int)  {
	if oldNode, ok := c.mapper[key]; !ok {
		newNode := &DoublyLinkedNode{
			key: key,
			value: value,
		}
		c.mapper[key] = newNode
		c.addToHead(newNode)
		c.size++
		if c.size > c.capacity {
			delete(c.mapper, c.tail.previous.key)
			c.size--
			c.removeNode(c.tail.previous)
		}
	} else {
		oldNode.value = value
		if c.head.next != oldNode {
			c.removeNode(oldNode)
			c.addToHead(oldNode)
		}
	}
}



func main() {
	// ["LRUCache","put","put","get","put","get","put","get","get","get"]
	// [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
	cache := Constructor(2)
	cache.Put(1, 1)
	cache.Put(2, 2)
	cache.Get(1)
	cache.Put(3, 3)
	cache.Get(2)
	cache.Put(4, 4)
}
